/**
 * 200. 岛屿数量
 * https://leetcode-cn.com/problems/number-of-islands/
 */

/**
 * @param {string[][]} grid
 * @param {number} i
 * @param {number} j
 */
function sign(grid, i, j) {
  if (!grid[i]) return;
  const char = grid[i][j];
  if (char !== '1') return;
  grid[i][j] = '0';
  sign(grid, i - 1, j);
  sign(grid, i, j - 1);
  sign(grid, i + 1, j);
  sign(grid, i, j + 1);
}

/**
 * @param {string[][]} grid
 * @return {number}
 */
function numIslands(grid) {
  const { length: n } = grid;
  const { length: m } = grid[0];
  let count = 0;
  for (let i = 0; i < n; i += 1) {
    for (let j = 0; j < m; j += 1) {
      if (grid[i][j] === '1') {
        count += 1;
        sign(grid, i, j);
      }
    }
  }
  return count;
}

console.log(numIslands([
  ['1', '1', '1', '1', '0'],
  ['1', '1', '0', '1', '0'],
  ['1', '1', '0', '0', '0'],
  ['0', '0', '0', '0', '0'],
]) === 1);
console.log(numIslands([
  ['1', '1', '0', '0', '0'],
  ['1', '1', '0', '0', '0'],
  ['0', '0', '1', '0', '0'],
  ['0', '0', '0', '1', '1'],
]) === 3);
